//最短路径 因为此题目规定了每一条边（u,v)起点编号小于终点编号（u<v)
//故可简单地动态规划
#include <iostream>
#include <climits>
using namespace std;

const int MAXN=20;
int n;
int cost[MAXN+1][MAXN+1];
int mincost[MAXN+1];//mincost[i]表示城市i到城市n的最省费用
int nextindex[MAXN+1];//nextindex[i]最省费用路径中，下一个城市的编号 

int main(){
    cin>>n;
    for(int u=1;u<=n;u++)
        for(int v=1;v<=n;v++) cin>>cost[u][v];
    //动规边界初始化
    for(int u=1;u<=n;u++) mincost[u]=INT_MAX;
    mincost[n]=0;
    nextindex[n]=0;
    //结点从大到小计算
    for(int u=n-1;u>=1;u--)
        for(int v=u+1;v<=n;v++){
            if (cost[u][v]>0&&(mincost[v]+cost[u][v]<mincost[u])){
                mincost[u]=mincost[v]+cost[u][v];
                nextindex[u]=v;
            }
        }
    
    cout<<mincost[1]<<endl;
    int u=1;
    while(u>0){
        cout<<u<<' ';
        u=nextindex[u];
    }
}